/*
题目: 单词划分Ⅱ
给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

注意：词典中的同一个单词可能在分段中被重复使用多次。

https://leetcode.cn/problems/word-break-ii
 */
public class WordBreak {
    List<String> src = new ArrayList<> ();
    int n;

    public List<String> wordBreak(String s, List<String> wordDict) {
        // 回溯: 划分问题
        Set<String> dict = new HashSet<> ();
        for (String x : wordDict)
            dict.add(x);

        n = s.length();

        backTrack(s, dict, 0, new LinkedList<> ());
        return src;
    }

    private void backTrack(String s, Set<String> dict, int pos, List<String> path) {
        if (pos >= n) {
            src.add(changeTo(path));
            return ;
        }
        for (int i = pos; i < n; i ++) {
            if (dict.contains(s.substring(pos, i + 1))) {
                path.add(s.substring(pos, i + 1));
                backTrack(s, dict, i + 1, path);
                path.remove(path.size() - 1);
            }
        }
    }

    private String changeTo(List<String> path) {
        String cur = "";
        int size = path.size();
        for (int i = 0; i < size - 1; i ++) {
            cur += path.get(i);
            cur += " ";
        }
        cur += path.get(size - 1);
        return cur;
    }
}
